The present invention relates to data storage devices and, more particularly, to error correction in data storage devices such as flash memory devices.
Flash memories are by far the most important type of electronic non-volatile memories (NVMs), accounting for nearly 90% of the NVM market. See, for example, the Web site of Saifun Semiconductors Ltd. (available at www.saifun.com) and Web-Feet Research, Inc. (available at www.web-feetresearch.com). Today, billions of flash memories are used in mobile, embedded, and mass-storage systems, mainly because of their high performance and physical durability. See, for example, P. Cappelletti et al., Chapter 5, “Memory Architecture and Related Issues” in Flash memories, Kluwer Academic Publishers, 1st Edition, 1999; and E. Gal and S. Toledo, ACM Computing Surveys, 37(2): 138-163 (2005). Well-known applications of flash memories include cell phones, digital cameras, USB flash drives, computers, sensors, and many more. They are now also replacing magnetic disks as hard disks, such as the 64 GB hard disk by SanDisk (see “SanDisk launches 64 gigabyte solid state drives for notebook PCs, meeting needs for higher capacity,” available at the Web site URL of http://biz.yahoo.com/cnw/070604/sandisk.html?.v=1). See also the Web article on the 256 GB hard disk by PQI (“PQI unveils 256 GB solid state drive,” available at the URL of www.guru3d.com/newsitem.php?id=5392). Based on the popular floating-gate technology, the dominance of flash memories is likely to continue.
However, there exist critical problems limiting the improvement of flash memories with respect to their speed, reliability, longevity, and storage capacity. Flash memories have a limited lifetime due to the quality degradation caused by block erasures; a flash memory can endure only about 105˜106 block erasures before it becomes no longer usable (see S. Aritome et al., Proceedings of the IEEE, 81(5):776-788 (1993), and P. Cappelletti et al., ibid. Removing charge from any single cell for data modification requires the block to be erased and all the 105 or so cells in it to be reprogrammed (or programmed to another block). The writing speed is constrained by a conservative cell-programming process that is about ten times slower than reading. The purpose of such conservative programming is to avoid over-programming, a serious error correctable only by block erasure and reprogramming. Data reliability is limited by errors caused by charge leakage, disturbs, and the like. See S. Aritome et al., ibid; P. Cappelletti et al., ibid; and P. Pavan et al., Proceedings of The IEEE, 85(8):1248-1271 (August 1997). The errors become more common when multi-level cells are used to increase the storage capacity.
New data storage modulation techniques that make more efficient use of the data storage cells in memory devices would be useful. Such new techniques should reduce the ill effects of over-programming of cells and increase the speed of data access.
New data storage modulation techniques will generate different types of error modalities as compared with conventional data storage modulation schemes. Systems that implement new data storage techniques will require error correction techniques tailored for the new modulation techniques.
From the discussion above, it should be apparent that there is a need for new error correction techniques that can recover from transmission errors resulting from new data modulation techniques and from errors in charge levels. The present invention satisfies these needs.